package com.linchong.heap.easy;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-12-05 11:20
 * @Description: KthLargestElementInStream$703
 * 设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
 *
 * 请实现 KthLargest 类：
 *
 * KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
 * int add(int val) 返回当前数据流中第 k 大的元素。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream
 *
 */
public class KthLargestElementInStream {

	static class KthLargest {

		private PriorityQueue<Integer> priorityQueue;

		private int[] nums;

		private int k;
		public KthLargest(int k, int[] nums) {
			this.k = k;
			this.nums = nums;
			this.priorityQueue = new PriorityQueue<>(k);

			int n = nums.length;
			for (int i = 0; i < n; i++) {
				if(i<k){
					priorityQueue.add(nums[i]);
				}else{
					int top = priorityQueue.peek();
					if(nums[i]>top){
						priorityQueue.poll();
						priorityQueue.add(nums[i]);
					}
				}
			}
		}

		public int add(int val) {
			int n = priorityQueue.size();
			if(n<k){
				priorityQueue.add(val);
			}else{
				int top = priorityQueue.peek();
				if(val>top){
					priorityQueue.poll();
					priorityQueue.add(val);
				}
			}
			return priorityQueue.peek();
		}

	}

	public static void main(String[] args) {
		int k = 1;
		int[] nums = {};
		KthLargest instance = new KthLargest(k,nums);
		System.out.println(instance.add(-3));
		System.out.println(instance.add(-2));
		System.out.println(instance.add(-4));
		System.out.println(instance.add(0));
		System.out.println(instance.add(4));
	}
}
